import java.util.Scanner;

/**
 * Created by L.jp
 * Description:
 *
 * NowCoder号称自己已经记住了1-100000之间所有的斐波那契数。
 * 为了考验他，我们随便出一个数n，让他说出第n个斐波那契数。当然，斐波那契数会很大。因此，如果第n个斐波那契数不到6位，则说出该数；否则只说出最后6位。
 *
 * 输入描述:
 * 输入有多组数据。
 * 每组数据一行，包含一个整数n (1≤n≤100000)。
 *
 *
 * 输出描述:
 * 对应每一组输入，输出第n个斐波那契数的最后6位。
 * User: 86189
 * Date: 2022-03-30
 * Time: 16:22
 */
public class Main {
    //首先我们要自己构造一个斐波那契数列，用一个容量100000的数组存储他们，又因为结果只要6位数，所以我们对于不到6位的就要输出这个数，对于超过6位
    //的就要输出最后6位，

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        long[] nums=new long[100000];
        nums[0]=1;
        nums[1] = 2;
        //创建一个变量统计什么时候开始斐波那契数数位超过6位
        int count=0;
        for(int i = 2;i<100000;i++){
            nums[i] = nums[i-1]+nums[i-2];
            if( count==0 && nums[i]>=1000000){ //count==0这个是必要条件，只有count==0时才是第一次超过6位，且只需判断一次，之后count都不是0
                count=i+1;
            }
            nums[i]=nums[i]%1000000; //取后6位
        }
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            long ret = nums[n - 1];
            if (n < count) {
                System.out.printf("%d\n",ret);
            } else if(n>count){
                System.out.printf("%06d\n",ret); //超过6位时需要有前导0
            }
        }
    }
}
